/* ver: 0.1, date 04-01-2008 by Marcel Hekman
 * - Initial implementation
 * 		- Implemented initialise, isDone, tick, fillOneGap and tryElement
 * ver: 0.2, date 05-01-2008 by Marcel Hekman
 * - Now using posX for a less 'jumpy' algorithm.
 */

package mazeAssignment;

public class DeadendFillSolve implements Solve
{
	private Maze maze;
	private boolean isFinished;
	private int posX, posY;
	
	@Override
	public void initialise(Maze m) throws SolveException
	{
		this.maze = m;
		this.isFinished = false;
		this.posX = 0;
		this.posY = 0;
	}

	@Override
	public boolean isDone()
	{
		return isFinished;
	}

	@Override
	public void tick() throws SolveException
	{
		if(isFinished)
			throw new SolveException("DeadendFillSolve.tick(): Already finished!");
		
		boolean hasChangedAField = fillOneGap();
		
		//We're at the end of the maze start from the beginning.
		if(!hasChangedAField)
		{
			//Reset the current row number.
			posX = 0;
			posY = 0;
			hasChangedAField = fillOneGap();
			
			//A full run changed nothing, so we're finished.
			if(!hasChangedAField)
			{
				isFinished = true;
				return;
			}
		}
	}
	
	/**
	 * Searches the entire maze for a dead-end element.
	 * Saves and resumes from a previously saved row.
	 * And start from the beginning if we reach the end. (only start from the beginning once)
	 * @return True if a gap was filled.
	 * If not the algorithm is finished because it cannot fill anymore gaps.
	 */
	private boolean fillOneGap()
	{
		int xSize = maze.getSizeX();
		int ySize = maze.getSizeY();
		
		//Continue from the last position
		for(int y = posY; y < ySize; y++)
		{
			for(int x = posX; x < xSize; x++)
			{
				if(tryElement(x, y))
				{
					//Save the current row number.
					posX = x;
					posY = y;
					return true;
				}
			}
			//Reset the x position so it won't make a curve shape during solve.
			posX = 0;
		}
		
		return false;
	}
	
	/**
	 * Checks if a node is a is a dead end.
	 * @param x Coordinate.
	 * @param y Coordinate.
	 * @return True if the element is a dead-end and marked. Else false.
	 */
	private boolean tryElement(int x, int y)
	{
		MazeElement current = maze.getElement(x, y);
		
		//SOLVE_START and SOLVE_END are obviously not a dead end.
		//Skip SOLVE_INVALID too because it is already marked.
		if(current.getSolveState() == MazeElement.SOLVE_START
		|| current.getSolveState() == MazeElement.SOLVE_END
		|| current.getSolveState() == MazeElement.SOLVE_INVALID)
		{
			return false;
		}
		
		int xSize = maze.getSizeX();
		int ySize = maze.getSizeY();
		
		//Count all accessible directions.
		int blockedDirections = 0;
		
		//North
		if(y == 0 || current.getNorth()
		|| maze.getElement(x, y-1).getSolveState() == MazeElement.SOLVE_INVALID)
		{
			blockedDirections++;
		}
		
		//East
		if(x+1 == xSize || current.getEast()
		|| maze.getElement(x+1, y).getSolveState() == MazeElement.SOLVE_INVALID)
		{
			blockedDirections++;
		}
		
		//South
		if(y+1 == ySize || current.getSouth()
		|| maze.getElement(x, y+1).getSolveState() == MazeElement.SOLVE_INVALID)
		{
			blockedDirections++;
		}
		
		//West
		if(x-1 == xSize || current.getWest()
		|| maze.getElement(x-1, y).getSolveState() == MazeElement.SOLVE_INVALID)
		{
			blockedDirections++;
		}
		
		//A dead end
		if(blockedDirections > 2)
		{
			current.markAsInvalid();
			return true;
		}
		else
		{
			return false;
		}
	}
}
